package com.lmz.project.redis.interview;


/**
 * 计算两个正序数组的中位数
 */
public class CalculateMedianCopy {
    public static void main(String[] args) {
//        int[] num1 = {2,2,4,4};
        int[] num1 = {1,3};
        int[] num2 ={2};
        double medianSortArrays = findMedianSortArrays(num1, num2);
        System.out.println(medianSortArrays);
    }


    public static double findMedianSortArrays(int[] num1, int[] num2) {
        //保证num1是长度较小数组
        if (num1.length > num2.length) {
            return findMedianSortArrays(num2, num1);
        }
        int x = num1.length;
        int y = num2.length;
        int left = 0;
        int right = x;

        while (left <= right) {
            int partitionX = (left + right) / 2;
            int partitionY = (x + y + 1) / 2 - partitionX;

            int maxX = (partitionX == 0) ? Integer.MIN_VALUE : num1[partitionX - 1];
            int minX = (partitionX == x) ? Integer.MAX_VALUE : num1[partitionX];

            int maxY = (partitionY == 0) ? Integer.MIN_VALUE : num2[partitionY - 1];
            int minY = (partitionY == y) ? Integer.MAX_VALUE : num2[partitionY];

            if (maxX <= minY && maxY <= minX) {
                if ((x+y) %2 ==0){
                    return (Math.max(maxX,maxY) + Math.min(minX,minY)) /2.0;
                }else {
                    return Math.max(maxX,maxY);
                }
            }else if (maxX > minY) {
                right = partitionX -1;
            }else {
                left = partitionX +1 ;
            }
        }
        throw new IllegalArgumentException("Input arrays are not sorted or empty.");
    }
}
